"""
https://leetcode.cn/problems/multiply-strings/
43. 字符串相乘
中等
相关标签
相关企业
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。



示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"


提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
"""

from typing import List


class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        """
        思路比较多，
        思路1：先转换为二进制，再相乘，再转化为十进制的方式
        思路2：直接用实际值相乘的直接思路
        """
        rev_num1=num1[::-1]
        rev_num2=num2[::-1]

        pos_num_list=list()
        for idx1 in range(len(rev_num1)):
            chr1=rev_num1[idx1]
            for idx2 in range(len(rev_num2)):
                chr2=rev_num2[idx2]
                acc=int(chr1)*int(chr2)
                pos=idx1+idx2
                self.put_pos_num(pos_num_list,pos,acc)

        res:List[str]=list()
        i=0
        while i<len(pos_num_list):

            num_str=str(pos_num_list[i])
            res.append(num_str[-1])

            if len(num_str)>1:
                self.put_pos_num(pos_num_list,i+1,int(num_str[:-1]))

            i+=1
        
        while len(res)>1 and res[-1]=='0':
            res.pop()
        
        return ''.join(reversed(res))

    def put_pos_num(self, pos_num_list:List[int],pos:int,acc:int)->None:
        while len(pos_num_list)-1<=pos:
            pos_num_list.append(0)

        pos_num_list[pos]+=acc

    def multiply2(self, num1: str, num2: str) -> str:
        """
        官方最快解法
        利用了python的int数字无论多大都可以相乘
        """
        m = 0
        n = 0
        for i in num1:
            m = m * 10
            m += int(i)-int('0')
        for i in num2:
            n = n * 10
            n += int(i)-int('0')
        
        return str(m * n)

if __name__ == '__main__':
    sol=Solution()
    num1="123456789123456789123456789123456789"
    num2="123456789123456789123456789123456789"
    res=sol.multiply2(num1,num2)

    print(res)